home *** CD-ROM | disk | FTP | other *** search
/ Amiga Collections: Taifun / Taifun 029 (1987-08-15)(Ossowski, Stefan)(DE)(PD).zip / Taifun 029 (1987-08-15)(Ossowski, Stefan)(DE)(PD).adf / Utilities / FComp / FComp.c < prev    next >
C/C++ Source or Header  |  1978-08-10  |  7KB  |  310 lines
  1. /* FCOMP.C - A File Comparison Program
  2.  *
  3.  * Source:      A File Comparison Program
  4.  *              Webb Miller and Eugene W. Myers
  5.  *              SOFTWARE - PRACTICE AND EXPERIENCE
  6.  *              Vol. 15(11), 1025-1040
  7.  *              November, 1985
  8.  *              Copyright John Wiley & Sons, Ltd.
  9.  *
  10.  * Usage:       fcomp [-n] file1 file2
  11.  *
  12.  *              where the optional flag "n" is an integer constant
  13.  *              that limits the size of edit scripts that will be
  14.  *              considered by fcomp. If all edit scripts changing
  15.  *              file1 to file2 contain more than "n" insertions
  16.  *              and deletions, then a message to that effect is
  17.  *              all that is printed. If no "n" is specified, then
  18.  *              arbitrarily long scripts may be considered.
  19.  */
  20.  
  21. /*** Include Files ***/
  22.  
  23. #include <stdio.h>
  24.  
  25. /*** Definitions ***/
  26.  
  27. #define MAXLINES  2000      /* Maximum # of lines in a file */
  28. #define ORIGIN    MAXLINES  /* Subscript for diagonal zero */
  29. #define INSERT    1
  30. #define DELETE    2
  31.  
  32. /*** Structures ***/
  33.  
  34. /* Edit scripts are stored in linked lists */
  35.  
  36. struct edit
  37. {
  38.   struct edit *link;    /* Previous edit command */
  39.   int op;               /* INSERT or DELETE */
  40.   int line1;            /* Line number in file1 */
  41.   int line2;            /* Line number in file2 */
  42. };
  43.  
  44. /*** Global Variables ***/
  45.  
  46. char *A[MAXLINES],      /* Ptrs. to lines of file1 and file2 */
  47.      *B[MAXLINES];
  48.  
  49. /*** Main Body of Program ***/
  50.  
  51. int main(argc,argv)
  52. int argc;
  53. char **argv;
  54. {
  55.   int max_d,    /* Bound on size of edit script */
  56.       m,        /* Number of lines in file1 */
  57.       n,        /* Number of lines in file2 */
  58.       lower,    /* Left-most diagonal under consideration */
  59.       upper,    /* Right-most diagonal under consideration */
  60.       d,        /* Current edit distance */
  61.       k,        /* Current diagonal */
  62.       row,      /* Row number */
  63.       col;      /* Column number */
  64.  
  65.   /* For each diagonal, two items are saved */
  66.  
  67.   int last_d[2*MAXLINES+1];     /* Row containing last d */
  68.   struct edit *script[2*MAXLINES+1];  /* Corresponding edit script */
  69.  
  70.   struct edit *new;
  71.   char *malloc();
  72.   void put_scr(),
  73.        fatal(),
  74.        exceed();
  75.  
  76.   if(argc > 1 && argv[1][0] == '-')
  77.   {
  78.     max_d = atoi(&argv[1][1]);
  79.     ++argv;
  80.     --argc;
  81.   }
  82.   else
  83.     max_d = 2*MAXLINES;
  84.  
  85.   if(argc != 3)
  86.     fatal("FCOMP requires two file names.");
  87.  
  88.   /* Read in file1 and file2 */
  89.  
  90.   m = in_file(argv[1],A);
  91.   n = in_file(argv[2],B);
  92.  
  93.   /* Initialize: 0 entries in D indicate identical prefixes */
  94.  
  95.   for(row = 0; row < m && row < n && strcmp(A[row],B[row]) == 0; ++row)
  96.     ;
  97.  
  98.   last_d[ORIGIN] = row;
  99.   script[ORIGIN] = NULL;
  100.   lower = (row == m) ? ORIGIN + 1 : ORIGIN - 1;
  101.   upper = (row == n) ? ORIGIN - 1 : ORIGIN + 1;
  102.   if(lower > upper)
  103.   {
  104.     puts("The files are identical.");
  105.     exit(0);
  106.   }
  107.  
  108.   /* For each value of the edit distance */
  109.  
  110.   for(d = 1; d <= max_d; ++d)
  111.   {
  112.     /* For each relevant diagonal */
  113.  
  114.     for(k = lower; k <= upper; k += 2)
  115.     {
  116.       /* Get space for next edit instruction */
  117.  
  118.       new = (struct edit *)malloc(sizeof(struct edit));
  119.       if(!new)
  120.         exceed(d);
  121.  
  122.       /* Find a d on diagonal k */
  123.  
  124.       if(k == ORIGIN-d || k != ORIGIN+d && last_d[k+1] >= last_d[k-1])
  125.       {
  126.         /* Moving down from the last d-1 on diagonal k+1 puts you
  127.          * farther along diagonal k than does moving right from the
  128.          * last d-1 on diagonal k-1.
  129.          */
  130.  
  131.         row = last_d[k+1]+1;
  132.         new->link = script[k+1];
  133.         new->op = DELETE;
  134.       }
  135.       else
  136.       {
  137.         /* Move right from the last d-1 on diagonal k-1 */
  138.  
  139.         row = last_d[k-1];
  140.         new->link = script[k-1];
  141.         new->op = INSERT;
  142.       }
  143.  
  144.       /* Code common to the two cases */
  145.  
  146.       new->line1 = row;
  147.       new->line2 = col = row + k - ORIGIN;
  148.       script[k] = new;
  149.  
  150.       /* Slide down the diagonal */
  151.  
  152.       while(row < m && col < n && strcmp(A[row],B[col]) == 0)
  153.       {
  154.         ++row;
  155.         ++col;
  156.       }
  157.       last_d[k] = row;
  158.  
  159.       if(row == m && col == n)
  160.       {
  161.         /* Hit southeast corner, have the answer */
  162.  
  163.         put_scr(script[k]);
  164.         exit(0);
  165.       }
  166.       if(row == m)  /* Hit last row, don't look to left */
  167.         lower = k+2;
  168.       if(col == n)  /* Hit last column, don't look to right */
  169.         upper = k-2;
  170.     }
  171.     --lower;
  172.     ++upper;
  173.   }
  174.   exceed(d);
  175. }
  176.  
  177. /*** Functions ***/
  178.  
  179. /* IN_FILE() - Read in a file and return a count of the lines */
  180.  
  181. int in_file(filename,P)
  182. char *filename,
  183.      *P[];
  184. {
  185.   char buf[100],
  186.        *malloc(),
  187.        *fgets(),
  188.        *save,
  189.        *b;
  190.   FILE *fp,
  191.        *fopen();
  192.   int lines = 0;
  193.  
  194.   if(!(fp = fopen(filename,"r")))
  195.   {
  196.     fprintf(stderr,"Cannot open file %s.\n",filename);
  197.     exit(1);
  198.   }
  199.   while(fgets(buf,100,fp))
  200.   {
  201.     if(lines >= MAXLINES)
  202.       fatal("File is too large for FCOMP.");
  203.     if(!(save = malloc(strlen(buf)+1)))
  204.       fatal("Not enough memory to save the files.");
  205.     P[lines++] = save;
  206.     for(b = buf; *save++ = *b++; )      /* Copy the line */
  207.       ;
  208.   }
  209.   fclose(fp);
  210.   return(lines);
  211. }
  212.  
  213. /* PUT_SCR() - Print the edit script */
  214.  
  215. void put_scr(start)
  216. struct edit *start;
  217. {
  218.   struct edit *ep,
  219.               *behind,
  220.               *ahead,
  221.               *a,
  222.               *b;
  223.   int change;
  224.  
  225.   /* Reverse the pointers */
  226.  
  227.   ahead = start;
  228.   ep = NULL;
  229.   while(ahead)
  230.   {
  231.     behind = ep;
  232.     ep = ahead;
  233.     ahead = ahead->link;
  234.     ep->link = behind;  /* Flip the pointer */
  235.   }
  236.  
  237.   /* Print the commands */
  238.  
  239.   while(ep)
  240.   {
  241.     b = ep;
  242.     if(ep->op == INSERT)
  243.       printf("Inserted after line %d:\n",ep->line1);
  244.     else
  245.     {
  246.       do        /* DELETE */
  247.       {
  248.         /* Look for a block of consecutive deleted lines */
  249.  
  250.         a = b;
  251.         b = b->link;
  252.       }
  253.       while(b && b->op == DELETE && b->line1 == a->line1 + 1);
  254.  
  255.       /* Now b points to the command after the last deletion */
  256.  
  257.       if(change = (b && b->op == INSERT && b->line1 == a->line1))
  258.         printf("Changed ");
  259.       else
  260.         printf("Deleted ");
  261.  
  262.       if(a == ep)
  263.         printf("line %d:\n",ep->line1);
  264.       else
  265.         printf("lines %d-%d:\n",ep->line1,a->line1);
  266.  
  267.       /* Print the deleted lines */
  268.  
  269.       do
  270.       {
  271.         printf(" %s",A[ep->line1 - 1]);
  272.         ep = ep->link;
  273.       }
  274.       while(ep != b);
  275.       if(!change)
  276.         continue;
  277.       printf("To:\n");
  278.     }
  279.  
  280.     /* Print the inserted lines */
  281.  
  282.     do
  283.     {
  284.       printf(" %s",B[ep->line2 - 1]);
  285.       ep = ep->link;
  286.     }
  287.     while(ep && ep->op == INSERT && ep->line1 == b->line1);
  288.   }
  289. }
  290.  
  291. /* FATAL() - Print error message and die */
  292.  
  293. void fatal(msg)
  294. char *msg;
  295. {
  296.   fprintf(stderr,"%s\n",msg);
  297.   exit(1);
  298. }
  299.  
  300. /* EXCEED() - The difference exceeds "d" */
  301.  
  302. void exceed(d)
  303. int d;
  304. {
  305.   fprintf(stderr,"The files differ in at least %d lines.\n",d);
  306.   exit(1);
  307. }
  308.  
  309. /*** End of FCOMP.C ***/
  310.